1. Field of the Invention
The invention relates generally to the field of computer networks comprising a plurality of stations which communicate data in a ring using a token-based protocol and, more specifically, to a mechanism for removing extraneous or erroneous data or ring control information from the network.
2. Description of the Prior Art
A computer network enables various devices, such as processors, mass storage devices, and printers, to communicate with each other over high speed communication links. The devices are connected, that is, coupled, to the network, and thus transfer data to and from the network through stations. The stations are interconnected by the communication links.
One example of such a network is a Local Area Network (LAN). A LAN allows high-bandwidth communication among devices within a limited geographic area. The communication links are typically composed of optical fibers, coaxial cable or twisted conductor pairs.
LANs may be configured as rings, with network stations transmitting data in one direction around the ring. Thus, when a station transmits data onto the ring, the data travels around the ring from station to station, with each station receiving the data from the preceding station and repeating it to the succeeding station, until the data reaches the station that is to receive it. In a well known ring network the receiving, or destination, station also repeats the data to its downstream successor and the data thus continues around the ring to the originating, or source, station.
The stations operate in accordance with communication protocols which facilitate the orderly transfer of data over the communication links. One type of communication protocol is a token ring system. Such systems use a token, that is, a specific string of bits, to indicate that a transmitting station has completed its transmission. A succeeding station may then, following the dictates of the protocol, begin transmitting data upon receipt of the token.
In a token ring system a station may not transmit data over the ring unless it actually holds the token. Thus if a station has data to transmit around the ring, the station removes the token from the ring data stream, that is, the station "captures" the token when it is received from the preceding station. The capturing station then begins its data transmission. When the station is finished with the data transmission it retransmits the token, effectively releasing it. The succeeding stations thereafter transfer the token around the ring until it is again captured by a station wishing to make a transmission.
Network stations transmit and receive data in the form of frames. The frames contain, in addition to the data, addresses, an error detection sequence and status flags, for example, a flag indicating receipt of the frame by the intended receiving, or destination, station. The frame addresses identify the source station and destination station or stations.
Every station and every attached device is identified by a unique address. Thus each station has associated with it its unique station-address and the addresses of its attached devices The stations may also have other addresses, for example, logical addresses, associated with them. A frame directed from a source station to a single destination station thus contains the address of the source station and, for example, the address of a specific device attached to the destination station. Each station may maintain a list of its associated addresses, such that the station receives the frames containing any one of its addresses.
A destination station, in addition to repeating the frame to its succeeding station, copies the frame for use by the appropriate device(s) associated with the station. The destination station may also set the applicable status flags indicating receipt of the frame.
When the frame has returned to the source station, the station, recognizing the frame as its own, for example, by recognizing the source address in the frame as its own, removes, or strips, the frame from the ring data stream. After a transmission, the first frames received by the source station over the ring are the frames it transmitted, assuming proper operation of the stations on the ring.
Frames may be altered by bit errors as they travel around the ring. The alteration may affect the source addresses in a number of frames, rendering them unrecognizable to the source stations The source stations will not then strip frames, and these frames will travel continuously around the ring. Thus a station listed as a destination station will repeatedly receive and process the frames. The processing will ordinarily detect the duplication, but it does require the use of station resources that might conflict with or delay other operations of the station.
A similar situation occurs when a station which has transmitted frames onto the ring becomes inoperative before it strips the transmitted frames. These frames, like the frames with altered source addresses, continuously travel around the ring because none of the stations then operating on the ring recognize the frames as their own and strip them. Accordingly, these frames, the altered-address frames and any other frames continuously traversing the ring are commonly referred to as "no-owner" frames. These frames may cause processing backlogs in the destination stations because the stations must process them each time they are received. The no-owner frames often require frequent and fast processing because they return to the destination stations in the time it takes the frames to traverse the ring, which is typically faster than frames are ordinarily received. Thus it is desirable to rid the ring of no-owner frames.
A mechanism to purge no-owner frames from rings operating under the IEEE 802.5 standard protocol involves stripping all data from the ring, and then re-initializing the ring. Re-initializing the ring causes it to perform all actions necessary to restart the ring and make it operational. For example, the initialization includes a claim token operation and the creation of a new token. The claim token operation involves an arbitration process during which the winner of arbitration, also called the claim token winner, creates the new token. Ring re-initialization may take a considerable period of time and result in lost performance during this period. Thus, for performance considerations, ring re-initializations should be performed as infrequently as possible.
To detect a no-owner frame, that is, to determine when a ring re-initialization is necessary, a station, referred to in the IEEE 802.5 standard protocol as an Active Monitor, places a marker at the beginning of each frame it repeats over the ring. If the Active Monitor thereafter detects a frame containing a marker, indicating that the frame traveled completely around the ring without being stripped, it begins a purge operation which includes a ring re-initialization. The marker is not protected by the frame error detection sequence. Thus an error in the marker may either start a purging operation unnecessarily or prevent one from occurring.
A purge operation begins with the Active Monitor placing a purge frame on the ring and then stripping everything off the ring that it receives. The Active Monitor may transmit multiple purge frames or it may transmit idle frames to fill the ring while it continues stripping everything, including the token, from the ring. When the Active Monitor receives one of its purge frames, indicating that it has essentially filled the ring with the purge and idle frames, it re-initializes the ring and issues a new token. Thus each purge operation causes the loss of all data then on the ring. In contrast, the purge operation described and claimed in the cross-referenced applications minimizes the loss of data on the ring and does not require ring re-initialization or interruption of ring operation.
The purge operation described above may be used only with ring protocols which allow markers to be placed at the beginning of a frame, for example, the IEEE 802.5 protocol. Prior to the inventions described in the cross-referenced applications, protocols such as the ANSI Fiber Distributed Data Interface (FDDI) protocol, which do not allow frame markers at the start of frames, did not have any mechanism to handle no-owner frames. The mechanism of the present invention may be used with any token ring protocol and any frame format.
Although the cross-referenced applications solve most of the problems relating to removal of no-owner frames from the network, there are two important aspects of no-owner frame stripping that these applications did not consider. First, when a token ring network is completely "idle," there is no need to purge no-owner frames, and in some cases it is disadvantageous to run a purging operation continually when the ring is idle. The purging operation requires the transmission of one or more void frames in each cycle, and the rate at which these void frames are generated can be as high as 333,000 frames per second. The term "idle ring" may be defined in various ways, as will be explained in more detail below.
The second, and related problem is that it may not be desirable to run a purging operation when the ring is near fully loaded. As with the term "idle" the term "near fully loaded" may be defined in different ways, but the same principle applies in each case. As will be explained in the detailed description below, the transmission of void frames during the purging operation uses a small fraction of the usable bandwidth of the ring. Moreover, if the ring is near fully loaded there is a higher probability that any no-owner frames will be stripped off without need for a purging station, by another station ,that is currently holding the token in normal operation, and is stripping incoming data while it transmits. Therefore, there is a need for further improvement in the purging of no-owner frames from token ring networks The present invention is directed to this end.